#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
    Splay tree rotation algorithm take into account both the parent and grandparent node!
    同时处理父亲和祖父节点.
    splay_search: splay tree的关键所在, 每次搜索到后, 要把值所在节点调节到树根.

    这里的实现没有保存parent字段, 主要靠在递归时传入parent参数来实现.
"""

class SplayTreeNode:
    '''
    用不到双旋, 只用递归左旋或者右旋即可.
    '''
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left, self.right = left, right
        self.cnt = 1

    def splay_search(self, val, parent):
        # return (new_root_node, contain_parent)
        # 对父节点parent和子节点承上启下

        if self.val == val:
            return self, False

        if val < self.val:
            searched_left, is_contain = self._search(self.left, val)
            # NOTE: is_contain 表示当前节点已经被rotate过了, 不再处理当前节点.
            if is_contain or (searched_left is None):
                return searched_left, False
            else:
                assert searched_left.val == val
                self.left = searched_left
                return self.rotate_child_left(parent), True
        else:
            searched_right, is_contain = self._search(self.right, val)
            if is_contain or (searched_right is None):
                return searched_right, False
            else:
                assert searched_right.val == val
                print('searched matched, searched %s self %s %s'  % (searched_right.val, self.val, getattr(parent, 'val', 'None')))
                self.right = searched_right
                return self.rotate_child_right(parent), True

    def _search(self, node, val):
        if node is None:
            return None, False
        return node.splay_search(val, parent=self)

    def insert(self, val):
        # print(val, self.val)
        if val == self.val:
            self.cnt += 1
            return

        if val < self.val:
            if self.left is None:
                self.left = SplayTreeNode(val)
            else:
                return self.left.insert(val)
        else:
            if self.right is None:
                self.right = SplayTreeNode(val)
            else:
                return self.right.insert(val)

    def rotate_child_left(self, parent):
        if parent is None:
            # parent 有可能是None, 表明当前节点是splay tree的root
            return self._rotate_left_left()

        if parent.left is self:
            return self.zig_child_left(parent)        # 一字型
        else:
            assert parent.right is self
            return self.zag_child_left(parent)        # 之字型

    def rotate_child_right(self, parent):
        print('rotate child right')
        if parent is None:
            # parent 有可能是None, 表明当前节点是splay tree的root
            return self._rotate_right_right()

        if parent.right is self:
            return self.zig_child_right(parent)        # 一字型
        else:
            assert parent.left is self
            return self.zag_child_right(parent)        # 之字型

    def _rotate_left_left(self):
        new_root = self.left
        self.left = new_root.right
        new_root.right = self
        return new_root

    def _rotate_right_right(self):
        new_root = self.right
        self.right = new_root.left
        new_root.left = self
        return new_root

    def zig_child_left(self, parent):
        # 一字型
        # 相当于先左旋self, 再左旋new_root
        new_root = self.left
        mid = self

        # 先左旋 parent
        # parent.left = mid.right
        # mid.right = parent

        # 再左旋 self
        # mid.left = new_root.right
        # new_root.right = mid
        # return new_root

        ret = parent._rotate_left_left()
        assert ret is self
        return self._rotate_left_left()

    def zig_child_right(self, parent):
        # 一字型: 可以手动, 也可以用两次右旋来实现.
        print('zig child right')
        # new_root = self.right
        # mid = self

        # parent.right = mid.left
        # mid.right = new_root.left

        # new_root.left = mid
        # mid.left = parent
        # return new_root

        ret = parent._rotate_right_right()
        assert ret is self
        return self._rotate_right_right()


    def zag_child_left(self, parent):
        # parent.right is self
        # self.left is new_root
        # 双旋(两次单旋)
        parent.right = self._rotate_left_left()
        return parent._rotate_right_right()

    def zag_child_right(self, parent):
        # parent.left is self
        # self.right is new_root
        # 双旋(两次单旋)
        parent.left = self._rotate_right_right()
        return parent._rotate_left_left()

    def rec_show(self):
        if self.left:
            self.left.rec_show()

        print(self.val, end=" ")

        if self.right:
            self.right.rec_show()

    def level_show(self):
        queue = []
        queue.append(self)

        while queue:
            l = len(queue)
            while l > 0:
                l -= 1
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                print(node.val, end=' ', sep=' ')

            print('')


class SplayTree:
    def __init__(self, root=None):
        self.root = root

    def insert(self, val):
        if self.root is None:
            self.root = SplayTreeNode(val)
        else:
            self.root.insert(val)

    def search(self, val):
        if self.root is None:
            return None

        if self.root.val == val:
            return self.root

        self.root, _ = self.root.splay_search(val, parent=None)
        return self.root

    def show(self):
        if self.root is not None:
            self.root.rec_show()
        print('\n===================  =====================')

    def level_show(self, s=''):
        if self.root is None:
            print('=================== empty tree %s=====================' % s)
        else:
            self.root.level_show()
            print('=================== level show of %s =====================' % (s))


def build_tree_from_str(str_tree):
    # '1,2,3,4,5'       # 1->2, 1->3, 2->4, 2->5
    # '1,2,#,#,#'       # 1->2, 1->#, 2->#, 2->#
    DELIMIT = ","
    results = str_tree.split(DELIMIT)

    # 注意输入的root可能为空
    # root = TreeNode(results.pop(0))
    root = _get_node(results.pop(0))
    if not root:
        return root

    tree_queue = [root]
    # "5,4,6,#,#,#,#"

    while results:
        node = tree_queue.pop(0)

        vl = results.pop(0)
        vr = results.pop(0)

        node.left  = _get_node(vl)
        node.right = _get_node(vr)
        if node.left:
            tree_queue.append(node.left)

        if node.right:
            tree_queue.append(node.right)

    return SplayTree(root)


def _get_node(value):
    if value == '#':
        return None

    return SplayTreeNode(int(value))


def test_splay_tree():
    t = SplayTree()
    for i in range(7, 0, -1):
        t.insert(i)

    t.show()


    t.search(1)
    print('root %s' % t.root.val)
    print('root.r %s' % t.root.right.val)
    print('root.r.r %s' % t.root.right.right.val)
    t.show()
    t.level_show()

    # ===================  =====================
    t = SplayTree()
    for i in range(32, 0, -1):        # page 94
        t.insert(i)

    # l = list( range(32) )
    # import random
    # random.shuffle(l)
    # print('list %s ' % l)
    # for i in l:
    #     t.insert(i)

    # tree_str = '1,#,32,30,#,28,31,26,29,#,#,24,27,#,#,22,25,#,#,20,23,#,#,18,21,#,#,16,19,#,#,14,17,#,#,12,15,#,#,10,13,#,#,8,11,#,#,6,9,#,#,4,7,#,#,2,5,#,#,#,3,#,#'
    # t = build_tree_from_str(tree_str)
    t.level_show()

    for i in range(1, 9+1):
    # for i in range(31, -1, -1):
        t.search(i)
        t.level_show('%s' % i)


def main():
    print("start main")
    test_splay_tree()

if __name__ == "__main__":
    main()
